package com.laotang.第_14_章_贪心算法.力扣_502_IPO;

import java.util.Arrays;
import java.util.PriorityQueue;

public class _502_ipo {

    // O(nlogn) + O(klogn) + O(nlogn)
    // O((n + k)logn)
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;

        int[][] arr = new int[n][2];

        for (int i = 0; i < n; ++i) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }

        // O(nlogn)
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);

        // 初始化一个大顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
        // O(knlogn)
        // 1 <= k <= 10^5
        // 1 <= n <= 10^5
        int curr = 0;
        // O(klogn)
        for (int i = 0; i < k; i++) {
            // 1. 拿到启动资金小于等于总资本的可选项目，并将其利润加入到大顶堆中
            // O(nlogn)
            // 这个 while 循环虽然在 for 循环中，但是这个 while 循环只会循环 n 次
            while (curr < n && arr[curr][0] <= w) {
                pq.add(arr[curr][1]);
                curr++;
            }

            // 2. 每次选取利润最大的那个项目(堆顶)
            if (!pq.isEmpty()) {
                // O(logn)
                w += pq.poll();
            } else {
                break;
            }
        }

        return w;
    }
}
